과거에 대한 기억도 없고, 미래를 예측할 수도 없는 시스템을 상상해 보세요. 이는 바로 조합 논리의 세계입니다. 여기서 디지털 회로는 피드백 루프나 내부 저장 장치의 복잡성을 갖지 않고, 특정 입력 신호 조합을 고유한 출력으로 즉시 변환하는 수학적 번역기 역할을 합니다. 이는 부울 대수의 가장 순수한 물리적 표현입니다.
논리의 재귀적 구조
복잡한 디지털 뇌를 만들기 위해, 우선 그 언어의 문법을 정의해야 합니다. 임의의 부울 대수 $(S, +, \cdot, ', 0, 1)$에서 우리는 부울 식 변수 집합 $x_1, \dots, x_n$ 위에서 구조적 귀납법을 통해 정의합니다:
기본 사례
1. $S$에 속하는 모든 상수 $s$는 부울 식입니다.
2. 모든 변수 $x_1, \dots, x_n$는 부울 식입니다.
재귀 단계
$X_1$와 $X_2$가 이미 부울 식이라면, 다음은 모두 유효한 식입니다:
$(X_1), \quad X_1', \quad X_1 + X_2, \quad X_1 \cdot X_2$
우선순위와 효율성
괄호가 없을 경우, 모호성을 피하기 위해 엄격한 우선순위 계층을 따릅니다: 합($\\land$) 항상 논리합($\\lor$)보다 우선합니다. 또한 하드웨어 설계를 최적화하기 위해 우리는 $n$-입력 게이트다중 2입력 게이트를 연결하는 대신, $a_1 \vee a_2 \vee \dots \vee a_n$를 하나의 논리 단위로 표현하여 전파 지연을 줄이고 회로 구조를 단순화합니다.
구조적 매핑 원리
모든 대수식은 실제 회로의 설계도입니다. $(x_1 \wedge (\neg x_2 \vee x_3)) \vee x_2$의 구조를 살펴보세요:
- 내부 층: 먼저 NOT 게이트와 OR 게이트를 사용하여 $(\neg x_2 \vee x_3)$를 분리합니다.
- 중간 층: 그 결과는 $x_1$의 신호와 함께 AND 게이트에 공급됩니다.
- 외부 층: 마지막으로, AND 출력과 원래의 $x_2$ 선이 종단 OR 게이트에서 만나게 됩니다.
🎯 핵심 원리
조합 회로의 구조는 부울 식의 연산 순서를 직접적인 물리적 반영합니다. 기억도 없고 피드백도 없으며, 순수하고 즉각적인 매핑만 존재합니다.